打开转盘锁(Leetcode 752)

发表于 | 分类于 ， ， | | 本文总阅读数 次
| 字数统计: 1.6k | 阅读时长 ≈ 7
Leetcode 752

1

题目分析

   这个题目是我非常推荐小伙伴们去做的一个题目，这个题目会做以后，BFS的类似题目应该都可以顺利求解

广度优先搜索

关于BFS的基本操作前面已经有大量的讲解和练习，这里不做过多介绍。推荐本题的原因是，这个题目包含了多次优化思想，虽然不能从理论上降低时间复杂度，但是这些剪枝操作在实际的测试样例中会节约大量的时间。

  1. 使用双向BFS进行求解，我们都知道BFS的时间复杂度为指数量级，对于m叉树来说为$O(m^n)$。因为每次都会扩展m倍的数据量。初始queue队列中仅有初始状态，第一次循环结束，初始状态弹出，会压入m个状态1，第二次循环结束，m个状态1弹出，会压入$m^2$个状态2，依此类推。所以我们要尽量减少n。本题中，一次解锁，可能产生8个状态，m = 8，极端情况下，target = “55555”，因此需要解锁20次，所以运算量为$8^20$，这是一个非常大的数。但是本题我们仅仅要搜索到target即可，在最后一次循环中，仅仅需要一个状态，因此我们可以从两端向中间搜索，从”0000”向target搜索一个循环，然后再从target向”0000”搜索一个循环，这样相当于将n减少为一半，此时运算量为$8^10$，这就极大降低了运行时间。

  2. 使用哈希表记录已经遍历过的状态，根据思路1选择了双向BFS，记从”0000”到target的队列为begin_queue，从target到”0000”的队列记为”end_queue”。从”0000”到target的寻找过程中，如果某个状态曾经出现过，可以停止搜索，因此使用begin_visited哈希表记录正向搜索过程中已经出现的状态。反向同理。这样状态最多出现$10^4$个，即从”0000”到”9999”，这种剪枝是最有效和常用的方法。往往可以将时间复杂度从指数降为线性。

  3. 第三种优化思路需要和第一种与第二种思路搭配使用，在双向BFS中，使用begin_visited和end_visited记录曾经遍历过的状态，当正向搜索时，某个状态K出现在end_visited中，说明找到了一条从”0000”到k和从target到k的通路，此时就可以直接返回当前的迭代次数，反向搜索同理

算法的**时间复杂度为$O(m^n \times n^2)$，空间复杂度为$O(m^n \times n)$**，其中m=10为转盘数字的进制，n=4为转盘数字的位数。

下面是C++语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead, beginVisited = { "0000" }, endVisited = { target };
        if (target == "0000") { return 0; }
        for (string s : deadends) { dead.insert(s); }
        if (dead.count("0000")) { return -1; }
        deque<string>* beginQueue = new deque<string>{ "0000" }, * endQueue = new deque<string>{ target };
        int times = 0;
        auto upChar = [](char c)->char { return c == '9' ? '0' : c + 1; };
        auto downChar = [](char c)->char { return c == '0' ? '9' : c - 1; };
        auto getStr = [=](string s)->vector<string> {
            vector<string> res;
            for (int i = 0; i < 4; i++) {
                char cur = s[i];
                s[i] = upChar(cur);
                res.push_back(s);
                s[i] = downChar(cur);
                res.push_back(s);
                s[i] = cur;
            }
            return res;
        };
        while (true) {
            times++;
            deque<string>* newBeginQueue = new deque<string>();
            while (!beginQueue->empty()) {
                string cur = beginQueue->front();
                beginQueue->pop_front();
                vector<string> curList = getStr(cur);
                for (string s : curList) {
                    if (!dead.count(s) && !beginVisited.count(s)) {
                        if (endVisited.count(s)) { return times; }
                        newBeginQueue->push_back(s);
                        beginVisited.insert(s);
                    }
                }
            }
            if (newBeginQueue->empty()) { return -1; }
            beginQueue = newBeginQueue;

            times++;
            deque<string>* newEndQueue = new deque<string>();
            while (!endQueue->empty()) {
                string cur = endQueue->front();
                endQueue->pop_front();
                vector<string> curList = getStr(cur);
                for (string s : curList) {
                    if (!dead.count(s) && !endVisited.count(s)) {
                        if (beginVisited.count(s)) { return times; }
                        newEndQueue->push_back(s);
                        endVisited.insert(s);
                    }
                }
            }
            if (newEndQueue->empty()) { return -1; }
            endQueue = newEndQueue;
        }
        return times;
    }
};

下面是Python语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
    def openLock(self, deadends, target):
        if target == '0000':
            return 0
        dead = set(deadends)
        if '0000' in dead:
            return -1
        begin_visited = set(['0000'])
        end_visited = set([target])
        begin_queue = deque(["0000"])
        end_queue = deque([target])
        times = 0

        def up_char(c):
            return str(int(c) + 1) if c != '9' else '0'

        def down_char(c):
            return str(int(c) - 1) if c != '0'else '9'

        def get_str(s):
            res = []
            for i in range(4):
                res.append(s[:i] + up_char(s[i]) + s[i + 1:])
                res.append(s[:i] + down_char(s[i]) + s[i + 1:])
            return res

        while True:
            times += 1
            new_begin_queue = deque()
            while begin_queue:
                cur = begin_queue.popleft()
                cur_list = get_str(cur)
                for x in cur_list:
                    if x not in dead and x not in begin_visited:
                        if x in end_visited:
                            return times
                        begin_visited.add(x)
                        new_begin_queue.append(x)
            if not new_begin_queue:
                return -1
            begin_queue = new_begin_queue

            times += 1
            new_end_queue = deque()
            while end_queue:
                cur = end_queue.popleft()
                cur_list = get_str(cur)
                for x in cur_list:
                    if x not in dead and x not in end_visited:
                        if x in begin_queue:
                            return times
                        end_visited.add(x)
                        new_end_queue.append(x)
            if not new_end_queue:
                return -1
            end_queue = new_end_queue

对比C++和Python两种语言，可以发现Python语言中，函数中可以嵌套定义函数，非常方便，在C++语言中函数无法嵌套定义，但是可以使用lambda表达式进行类似的操作。而且要注意的是在C++语言中，本层遍历后beginQueue要指向newBeginQueue，此时两个都应该设置为指针，否则newBeginQueue结束清空时，beginQueue也为空。而Python里面对象都是指针，因此直接赋值即可。

刷题总结

  本题的重点在于双向BFS的优化，而且小伙伴们一定要区分什么时候用BFS，什么时候用DFS，通常来说两个都可以使用，当求最短路的时候，要使用BFS，因为每一次循环代表往前进一步，第一次搜索到某个状态时，一定是最短的路径，这时如果使用DFS则需要将所有的通路都走一遍，才能找到最短的路径。当题目只需要寻找到一条通路时，往往使用DFS，因为BFS每次前进一步，假设最近为第n步，时间复杂度为$O(m^n)$，而且需要耗费$O(m^n)$的空间复杂度。但是使用DFS，可能第一次就找到通路，计算量为$O(n)$，空间复杂度为$O(n)$，表示栈空间的调用。

-------------本文结束感谢您的阅读-------------
0%